home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / answers / rec / puzzles / archive / competition / part1 < prev    next >
Encoding:
Text File  |  1993-08-18  |  42.3 KB  |  1,289 lines
  1. Newsgroups: rec.puzzles,news.answers,rec.answers
  2. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
  3. From: chris@questrel.com (Chris Cole)
  4. Subject: rec.puzzles Archive (competition), part 06 of 35
  5. Message-ID: <puzzles/archive/competition/part1_745653851@questrel.com>
  6. Followup-To: rec.puzzles
  7. Summary: This is part of an archive of questions
  8.  and answers that may be of interest to
  9.  puzzle enthusiasts.
  10.  Part 1 contains the index to the archive.
  11.  Read the rec.puzzles FAQ for more information.
  12. Sender: chris@questrel.com (Chris Cole)
  13. Reply-To: archive-comment@questrel.com
  14. Organization: Questrel, Inc.
  15. References: <puzzles/archive/Instructions_745653851@questrel.com>
  16. Date: Wed, 18 Aug 1993 06:04:40 GMT
  17. Approved: news-answers-request@MIT.Edu
  18. Expires: Thu, 1 Sep 1994 06:04:11 GMT
  19. Lines: 1267
  20. Xref: senator-bedfellow.mit.edu rec.puzzles:24992 news.answers:11512 rec.answers:1912
  21.  
  22. Archive-name: puzzles/archive/competition/part1
  23. Last-modified: 17 Aug 1993
  24. Version: 4
  25.  
  26.  
  27. ==> competition/contests/games.magazine.p <==
  28. What are the best answers to various contests run by _Games_ magazine?
  29.  
  30. ==> competition/contests/games.magazine.s <==
  31. Contest            Date        Archive Entry
  32. ----------------------    --------------    -----------------------------
  33. Equations        ? 1981        equations
  34. National Puzzle 1993    1993        npc.1993
  35. Nots and Crosses    ? 1992        nots.and.crosses
  36. Perfect Ladder        July 1993    perfect.ladder
  37. Telegrams        ?        telegrams
  38.  
  39. ==> competition/contests/national.puzzle/npc.1993.p <==
  40. What are the solutions to the Games magazine 1993 National Puzzle Contest?
  41.  
  42. ==> competition/contests/national.puzzle/npc.1993.s <==
  43. 1. 6, 10, 11, and 12 are in one group, and everything else is in the other.
  44. 2. 20
  45. 3. The upper-right segment of the first 8.
  46. 4. 6
  47. 5. d (ball point pen, analog watch, mattress, pogo stick): springs
  48. 6. a (Fire Engine, strawberry, lobster, lips): red
  49. 7. h (Icicle, paint, nose, faucet): drip
  50. 8. f (piggy bank, basketball, jack o' lantern, drum): hollow
  51. 9. g (horseshoe, goal post, stethoscope, fish hook): shaped like letters
  52. 10. e (flying bat, Xmas tree ornament, framed picture, trapeze artist): hang
  53. 11. b (candle, owl, vampire, pajamas): all associated with night
  54. 12. 4, 7, 2, 10, 5, 8, 1, 9, 6, 3
  55. 13. 152954
  56. 14. LIMA PERU
  57. 15. 44
  58. 16. 160
  59. 17. A
  60. 18. Flo Lisa Amy Joyce Kim. 
  61. 19. Top: AJKQ, 2nd Row: JKAQ, 3rd Row: KQAJ, 4th Row: JQAK
  62. 20. Joan Miro, Paavo Nurmi, Blaise Pascal
  63. 21. Top: 1, 8, 4  Middle: 6, 9, 3  Bottom: 2, 7, 5
  64. 22. d and g
  65. 23. Brenda: 87, Carrie: 85, Dick: 86, Harry: 84, Laura: 88, Tom: 83
  66. 24. If you number the columns 1-6 and letter the rows a-f, the first group
  67.     consists of 1a, 2a, 3a, 4a, 1b, 2b, 2c, 3c, 2d.  Other groups are
  68.     similarly shaped, rotated around the center point of the grid.
  69. 25. 2, 6, 5
  70. 26. Top: R O M  Middle: Q T A   Bottom: U E D S
  71. 27. 3 X 58 = 174 = 6 X 29
  72. 28. 5 (the number of enclosed areas in the letters of each month name)
  73. 29. too hard to describe -- easier than it looked
  74. 30. 80
  75. 31. 16
  76. 32. 4 (ADBECF ADBFCE ADFCBE BFDCAE)
  77. 33. 8 (delete 3,5,7,9,12,14,17,18)
  78. 34.  CONKP VALEY GSRCW TUIBI LANZS
  79.  
  80.  
  81. ==> competition/games/bridge.p <==
  82. Are there any programs for solving double-dummy Bridge?
  83.  
  84.  
  85. ==> competition/games/bridge.s <==
  86. I'll enclose my Double-Dummy solver for bridge.  I like this program
  87. because it contains a wildly unstructured "goto" -- which I claim is the
  88. most readable way to write the program.
  89.     Included are two test problems for the bridge-solver: a 6-card
  90. ending and a complete 13-card position.  The former should be very fast;
  91. the latter about 20 minutes on Sparcstation-2.  Each is *very*
  92. challenging for humans.
  93.  
  94. Regards, James
  95.  
  96. =============== clip; chmod +x; execute =============
  97. #!/bin/sh
  98. cat > bridge.c << 'EOF'
  99. /*
  100.  * DOUBLE_DUMMY
  101.  * Copyright (c) 1990 by
  102.  *    James D. Allen
  103.  *    19785 Stanton Ave
  104.  *    Castro Valley, CA
  105.  * Permission granted to use for any non-commercial purpose
  106.  *    as long as this notice is not removed.
  107.  *
  108.  * This program will solve double-dummy bridge problems.
  109.  * The algorithm is trivial: brute-force alpha-beta search (also known
  110.  *    as "backtracking").  The alpha-beta is trivial since we do not
  111.  *    consider overtricks or extra undertricks.
  112.  * The control flow is neat; this is a rare exception where software is
  113.  *    more readable with a "goto".  (Although I've tersified this to
  114.  *    the point where it is perhaps unreadable anyway :-)
  115.  */
  116.  
  117. #define    NUMP    4    /* The Players:  N, E, S, W */
  118. #define        NORTH    0
  119. #define        IS_CONT(x)    (!((x) & 1))    /* Is x on N/S team? */
  120. #define        LHO(x)        (((x) + 1) % NUMP)
  121. #define        RHO(x)        (((x) + NUMP - 1) % NUMP)
  122. char    *Playername[] = { "North", "East", "South", "West" };
  123.  
  124. #define    NUMS    4    /* The Suits:   S, H, D, C */
  125. char    Suitname[] = "SHDC";
  126. char    *Fullname[] = { "Spades\t", "Hearts\t", "Diamonds", "Clubs\t" };
  127.  
  128. /*
  129.  * Rank indices are 2 (Ace), 3 (King), ... 14 (Deuce)
  130.  * There is also a CARD Index which can be converted to from Rank and Suit.
  131.  */
  132. #define    CARD(Suit, Rank)    (((Suit) << 4) | (Rank))
  133. #define    SUIT(Card)        ((Card) >> 4)
  134. #define    RANK(Card)        ((Card) & 0xf)
  135. char    Rankname[] = "??AKQJT98765432";
  136. #define    INDEX(s, c)    ((char *)index(s, c) - (s))
  137.  
  138. /* A "SuitSet" is used to cope with more than one card at once: */
  139. typedef    unsigned short SuitSet;
  140. #define    MASK(Card)        (1 << RANK(Card))
  141. #define    REMOVE(Set, Card)    ((Set) &= ~(MASK(Card)))
  142.  
  143. /* And a CardSet copes with one SuitSet for each suit: */
  144. typedef struct cards {
  145.     SuitSet cc[NUMS];
  146. } CardSet;
  147.  
  148. /* Everything we wish to remember about a trick: */
  149. struct status {
  150.     CardSet st_hold[NUMP];    /* The players' holdings */
  151.     CardSet st_lgl[NUMP];    /* The players' remaining legal plays */
  152.     short    st_play[NUMP];    /* What the players played */
  153.     SuitSet st_trick;    /* Led-suit Cards eligible to win trick */
  154.     SuitSet st_trump;    /* Trump Cards eligible to win trick */
  155.     short    st_leader;    /* Who led to the trick */
  156.     short    st_suitled;    /* Which suit was led */
  157. }
  158. Status[14]; /* Status of 13 tricks and a red zone" */
  159. #define    Hold    Statp->st_hold
  160. #define    Resid    (Statp+1)->st_hold
  161. #define    Lgl    Statp->st_lgl
  162. #define    Play    Statp->st_play
  163. #define    Trick    Statp->st_trick
  164. #define    Trtrick    Statp->st_trump
  165. #define    Leader    Statp->st_leader
  166. #define    Suitled    Statp->st_suitled
  167.  
  168. /* Pick a card from the set and return its index */
  169. pick(set)
  170.     SuitSet set;
  171. {
  172.     return set & 0xff ? set &  1 ? 0 : set &  2 ? 1 : set &  4 ? 2
  173.               : set &  8 ? 3 : set & 16 ? 4 : set & 32 ? 5
  174.               : set & 64 ? 6 : 7 : pick(set >> 8) + 8;
  175. }
  176.  
  177. #define    highcard(set)    pick(set) /* Pick happens to return the best card */
  178.  
  179. main()
  180. {
  181.     register struct status *Statp = Status;    /* Point to current status */
  182.     int    tnum;    /* trick number */
  183.     int    won;    /* Total tricks won by North/South */
  184.     int    nc;    /* cards on trick */
  185.     int    ohsize;    /* original size of hands */
  186.     int    mask;
  187.     int    trump;
  188.     int    player;    /* player */
  189.     int    pwin;    /* player who won trick */
  190.     int    suit;    /* suit to play */
  191.     int    wincard; /* card which won the trick */
  192.     int    need;    /* Total tricks needed by North/South */
  193.     int    cardx;    /* Index of a card under consideration */
  194.     int    success; /* Was the trick or contract won by North/South ? */
  195.     int    last_t;    /* Decisive trick number */
  196.     char    asciicard[60];
  197.     SuitSet inplay;    /* cards still in play for suit */
  198.     SuitSet pr_set;    /* Temp for printing */
  199.  
  200.     /* Read in the problem */
  201.     printf("Enter trump suit (0-S,1-H,2-D,3-C,4-NT): ");
  202.     scanf("%d", &trump);
  203.     printf("Enter how many tricks remain to be played: ");
  204.     scanf("%d", &ohsize);
  205.     printf("Enter how many tricks North/South need to win: ");
  206.     scanf("%d", &need);
  207.     printf("Enter who is on lead now (0=North,etc.): ");
  208.     scanf("%d", &pwin);
  209.     printf("Enter the %d cards beginning with North:\n", NUMP * ohsize);
  210.     for (player = NORTH; player < NUMP; player++) {
  211.         for (tnum = 0; tnum < ohsize; tnum++) {
  212.             scanf("%s", asciicard);
  213.             cardx = CARD(INDEX(Suitname, asciicard[1]),
  214.                     INDEX(Rankname, asciicard[0]));
  215.             Hold[player].cc[SUIT(cardx)] |= MASK(cardx);
  216.         }
  217.     }
  218.  
  219.     /* Handle the opening lead */
  220.     printf("Enter the directed opening lead or XX if none:\n");
  221.     Lgl[pwin] = Hold[pwin];
  222.     scanf("%s", asciicard);
  223.     if (asciicard[0] == 'X') {
  224.         strcpy(asciicard, "anything");
  225.     } else {
  226.         cardx = CARD(INDEX(Suitname, asciicard[1]),
  227.                 INDEX(Rankname, asciicard[0]));
  228.         for (suit = 0; suit < NUMS; suit++)
  229.             if (suit != SUIT(cardx))
  230.                 Lgl[pwin].cc[suit] = 0;
  231.             else if (!(Lgl[pwin].cc[suit] &= MASK(cardx))) {
  232.                 printf("He can't lead card he doesn't have\n");
  233.                 exit(1);
  234.             }
  235.     }
  236.  
  237.     /* Print the problem */
  238.     for (player = NORTH; player < NUMP; player++) {
  239.         printf("\n---- %s Hand ----:\n", Playername[player]);
  240.         for (suit = 0; suit < NUMS; suit++) {
  241.             printf("\t%s\t", Fullname[suit]);
  242.             for (pr_set = Hold[player].cc[suit]; pr_set;
  243.                     REMOVE(pr_set, pick(pr_set)))
  244.                 printf("%c ", Rankname[RANK(pick(pr_set))]);
  245.             printf("\n");
  246.         }
  247.     }
  248.     printf("\n%s%s Trumps; %s leads %s; N-S want %d tricks; E-W want %d\n",
  249.         trump < NUMS ? Fullname[trump] : "",
  250.         trump < NUMS ? " are" : "No",
  251.         Playername[pwin], asciicard, need, ohsize + 1 - need);
  252.  
  253.       /* Loop to play tricks forward until the outcome is conclusive */
  254.     for (tnum = won = success = 0;
  255.             success ? ++won < need : won + ohsize >= need + tnum;
  256.             tnum++, Statp++, success = IS_CONT(pwin)) {
  257.         for (nc = 0, player = Leader = pwin; nc < NUMP;
  258.                     nc++, player = LHO(player)) {
  259.               /* Generate legal plays except opening lead */
  260.             if (nc || tnum)
  261.                 Lgl[player] = Hold[player];
  262.               /* Must follow suit unless void */
  263.             if (nc && Lgl[player].cc[Suitled])
  264.                 for (suit = 0; suit < NUMS; suit++)
  265.                     if (suit != Suitled)
  266.                         Lgl[player].cc[suit] = 0;
  267.             goto choose_suit; /* this goto is easily eliminated */
  268.               /* Comes back right away after choosing "suit"  */
  269.             make_play:
  270.             Play[player] = cardx =
  271.                 CARD(suit, pick(Lgl[player].cc[suit]));
  272.             if (nc == 0) {
  273.                 Suitled = suit;
  274.                 Trick = Trtrick = 0;
  275.             }
  276.               /* Set the play into "Trick" if it is win-eligible */
  277.             if (suit == Suitled)
  278.                 Trick |= MASK(cardx);
  279.             if (suit == trump)
  280.                 Trtrick |= MASK(cardx);
  281.  
  282.               /* Remove card played from player's holding */
  283.             Resid[player] = Hold[player];
  284.             REMOVE(Resid[player].cc[suit], cardx);
  285.         }
  286.  
  287.           /* Finish processing the trick ... who won? */
  288.         if (Trtrick)
  289.             wincard = CARD(trump, highcard(Trtrick));
  290.         else
  291.             wincard = CARD(Suitled, highcard(Trick));
  292.         for (pwin = 0; Play[pwin] != wincard; pwin++)
  293.             ;
  294.     }
  295.  
  296.       /* Loop to back up and let the players try alternatives */
  297.     for (last_t = tnum--, Statp--; tnum >= 0; tnum--, Statp--) {
  298.         won -= IS_CONT(pwin);
  299.         pwin = Leader;
  300.         for (player = RHO(Leader), nc = NUMP-1; nc >= 0;
  301.                     player = RHO(player), nc--) {
  302.               /* What was the play? */
  303.             cardx = Play[player];
  304.             suit = SUIT(cardx);
  305.               /* Retract the played card */
  306.             if (suit == Suitled)
  307.                 REMOVE(Trick, cardx);
  308.             if (suit == trump)
  309.                 REMOVE(Trtrick, cardx);
  310.               /* We also want to remove any redundant adjacent plays */
  311.             inplay =  Hold[0].cc[suit] | Hold[1].cc[suit]
  312.                 | Hold[2].cc[suit] | Hold[3].cc[suit];
  313.             for (mask = MASK(cardx); mask <= 0x8000; mask <<= 1)
  314.                 if (Lgl[player].cc[suit] & mask)
  315.                     Lgl[player].cc[suit] &= ~mask;
  316.                 else if (inplay & mask)
  317.                     break;
  318.               /* If the card was played by a loser, try again */
  319.             if (success ? !(IS_CONT(player)) : IS_CONT(player)) {
  320.                 choose_suit:
  321.                   /* Pick a suit if any untried plays remain */
  322.                 for (suit = 0; suit < NUMS; suit++)
  323.                     if (Lgl[player].cc[suit])
  324.                         /* This goto is really nice!! */
  325.                         goto make_play;
  326.             }
  327.         }
  328.     }
  329.  
  330.     /*
  331.      * We're done.  We know the answer.
  332.      * We can't remember all the variations; fortunately the
  333.      *  succeeders played correctly in the last variation examined,
  334.      * so we'll just print it.
  335.      */
  336.     printf("Contract %s, for example:\n",
  337.             success ? "made" : "defeated");
  338.     for (tnum = 0, Statp = Status; tnum < last_t; tnum++, Statp++) {
  339.         printf("Trick %d:", tnum + 1);
  340.         for (player = 0; player < Leader; player++)
  341.             printf("\t");
  342.         for (nc = 0; nc < NUMP; nc++, player = LHO(player))
  343.             printf("\t%c of %c",
  344.                 Rankname[RANK(Play[player])],
  345.                 Suitname[SUIT(Play[player])]);
  346.         printf("\n");
  347.     }
  348.     return 0;
  349. }
  350. EOF
  351. cc -O -o bridge bridge.c
  352. bridge << EOF
  353. 4 6 5 2
  354. AS JS 4S QD 8D 2C
  355. KS QS 9H 8H AD 2D
  356. AH 2H KD 9D 7D AC
  357. TS 3S 2S TH TD TC
  358. XX
  359. EOF
  360. bridge << EOF
  361. 1 13 13 3
  362. 3C          3H 2H              AD KD 2D    AS KS 7S 6S 5S 4S 3S
  363. 8C 7C 6C 5C 4C    QH TH 8H 7H          8D 7D 6D    2S
  364. AC QC JC 9C      AH KH JH 9H 6H 5H      5D 4D 3D
  365. KC TC 2C      4H              QD JD TD 9D    QS JS TS 9S 8S
  366. QS
  367. EOF
  368.  
  369.  
  370.  
  371. ==> competition/games/chess/knight.control.p <==
  372. How many knights does it take to attack or control the board?
  373.  
  374. ==> competition/games/chess/knight.control.s <==
  375. Fourteen knights are required to attack every square:
  376.  
  377.     1   2   3   4   5   6   7   8
  378.    ___ ___ ___ ___ ___ ___ ___ ___
  379. h |   |   |   |   |   |   |   |   |  
  380.    --- --- --- --- --- --- --- ---
  381. g |   |   | N | N | N | N |   |   |
  382.    --- --- --- --- --- --- --- ---
  383. f |   |   |   |   |   |   |   |   |
  384.    --- --- --- --- --- --- --- ---
  385. e |   | N | N |   |   | N | N |   |
  386.    --- --- --- --- --- --- --- ---
  387. d |   |   |   |   |   |   |   |   |
  388.    --- --- --- --- --- --- --- ---
  389. c |   | N | N | N | N | N | N |   |
  390.    --- --- --- --- --- --- --- ---
  391. b |   |   |   |   |   |   |   |   |
  392.    --- --- --- --- --- --- --- ---
  393. a |   |   |   |   |   |   |   |   |
  394.    --- --- --- --- --- --- --- ---
  395.  
  396. Three knights are needed to attack h1, g2, and a8; two more for b1, a2,
  397. and b3, and another two for h7, g8, and f7.
  398.  
  399. The only alternative pattern is:
  400.  
  401.     1   2   3   4   5   6   7   8
  402.    ___ ___ ___ ___ ___ ___ ___ ___
  403. h |   |   |   |   |   |   |   |   |  
  404.    --- --- --- --- --- --- --- ---
  405. g |   |   | N |   |   | N |   |   |
  406.    --- --- --- --- --- --- --- ---
  407. f |   |   | N | N | N | N |   |   |
  408.    --- --- --- --- --- --- --- ---
  409. e |   |   |   |   |   |   |   |   |
  410.    --- --- --- --- --- --- --- ---
  411. d |   |   | N | N | N | N |   |   |
  412.    --- --- --- --- --- --- --- ---
  413. c |   | N | N |   |   | N | N |   |
  414.    --- --- --- --- --- --- --- ---
  415. b |   |   |   |   |   |   |   |   |
  416.    --- --- --- --- --- --- --- ---
  417. a |   |   |   |   |   |   |   |   |
  418.    --- --- --- --- --- --- --- ---
  419.  
  420. Twelve knights are needed to control (attack or occupy) the board:
  421.  
  422.     1   2   3   4   5   6   7   8
  423.    ___ ___ ___ ___ ___ ___ ___ ___
  424. a |   |   |   |   |   |   |   |   |  
  425.    --- --- --- --- --- --- --- ---
  426. b |   |   | N |   |   |   |   |   |
  427.    --- --- --- --- --- --- --- ---
  428. c |   |   | N | N |   | N | N |   |
  429.    --- --- --- --- --- --- --- ---
  430. d |   |   |   |   |   | N |   |   |
  431.    --- --- --- --- --- --- --- ---
  432. e |   |   | N |   |   |   |   |   |
  433.    --- --- --- --- --- --- --- ---
  434. f |   | N | N |   | N | N |   |   |
  435.    --- --- --- --- --- --- --- ---
  436. g |   |   |   |   |   | N |   |   |
  437.    --- --- --- --- --- --- --- ---
  438. h |   |   |   |   |   |   |   |   |
  439.    --- --- --- --- --- --- --- ---
  440.  
  441. Each knight can control at most one of the twelve squares a1, b1, b2,
  442. h1, g1, g2, a8, b8, b7, h8, g8, g7.  This position is unique up to
  443. reflection.
  444.  
  445. References
  446.     Martin Gardner, _Mathematical Magic Show_.
  447.  
  448. ==> competition/games/chess/knight.most.p <==
  449. What is the maximum number of knights that can be put on n x n chessboard
  450. without threatening each other?
  451.  
  452. ==> competition/games/chess/knight.most.s <==
  453. n^2/2 for n even >= 4.
  454.  
  455. Divide the board in parts of 2x4 squares. The squares within
  456. each part are paired as follows:
  457.  
  458. -----
  459. |A|B|
  460. -----
  461. |C|D|
  462. -----
  463. |B|A|
  464. -----
  465. |D|C|
  466. -----
  467.  
  468. Clearly, not more than one square per pair can be occupied by a knight.
  469.  
  470. ==> competition/games/chess/knight.tour.p <==
  471. For what size boards are knight tours possible?
  472.  
  473. ==> competition/games/chess/knight.tour.s <==
  474. A tour exists for boards of size 1x1, 3x4, 3xN with N >= 7, 4xN with N >= 5,
  475. and MxN with N >= M >= 5.  In other words, for all rectangles except 1xN
  476. (excluding the trivial 1x1), 2xN, 3x3, 3x5, 3x6, 4x4.
  477.  
  478. With the exception of 3x8 and 4xN, any even-sized board which allows a tour
  479. will also allow a closed (reentrant) tour.
  480.  
  481. On an odd-sided board, there is one more square of one color than
  482. of the other.  Every time a knight moves, it moves to a square of
  483. the other color than the one it is on.  Therefore, on an odd-sided
  484. board, it must end the last move but one of the complete, reentrant
  485. tour on a square of the same color as that on which it started.
  486. It is then impossible to make the last move, for that move would end
  487. on a square of the same color as it begins on.
  488.  
  489. Here is a solution for the 7x7 board (which is not reentrant).
  490.      ------------------------------------
  491.      | 17 |  6 | 33 | 42 | 15 |  4 | 25 |
  492.      ------------------------------------
  493.      | 32 | 47 | 16 |  5 | 26 | 35 | 14 |
  494.      ------------------------------------
  495.      |  7 | 18 | 43 | 34 | 41 | 24 |  3 |
  496.      ------------------------------------
  497.      | 46 | 31 | 48 | 27 | 44 | 13 | 36 |
  498.      ------------------------------------
  499.      | 19 |  8 | 45 | 40 | 49 |  2 | 23 |
  500.      ------------------------------------
  501.      | 30 | 39 | 10 | 21 | 28 | 37 | 12 |
  502.      ------------------------------------
  503.      |  9 | 20 | 29 | 38 | 11 | 22 |  1 |
  504.      ------------------------------------
  505.  
  506. Here is a solution for the 5x5 board (which is not reentrant).
  507.      --------------------------
  508.      |  5 | 10 | 15 | 20 |  3 |
  509.      --------------------------
  510.      | 16 | 21 |  4 |  9 | 14 |
  511.      --------------------------
  512.      | 11 |  6 | 25 |  2 | 19 |
  513.      --------------------------
  514.      | 22 | 17 |  8 | 13 | 24 |
  515.      --------------------------
  516.      |  7 | 12 | 23 | 18 |  1 |
  517.      --------------------------
  518.  
  519. Here is a reentrant 2x4x4 tour:
  520.      0 11 16  3    15  4  1 22
  521.     19 26  9 24     8 23 14 27
  522.     10  5 30 17    31 12 21  2
  523.     29 18 25  6    20  7 28 13
  524. A reentrant 4x4x4 tour can be constructed by splicing two copies.
  525.  
  526. It shouldn't be much more work now to completely solve the problem of which 3D
  527. rectangular boards allow tours.
  528.  
  529. Warnsdorff's rule: at each stage of the knight's tour, choose the
  530. square with the fewest remaining exits:
  531.  
  532.  1 12 23 44  3 14 25
  533. 22 43  2 13 24 35  4
  534. 11 28 45 40 47 26 15
  535. 42 21 48 27 34  5 36
  536. 29 10 41 46 39 16 33
  537. 20 49  8 31 18 37  6
  538.  9 30 19 38  7 32 17
  539.  
  540. Mr. Beverley published in the Philosophical Magazine in 1848 this
  541. knight's tour that is also a magic square:
  542.  
  543.  1 30 47 52  5 28 43 54
  544. 48 51  2 29 44 53  6 27
  545. 31 46 49  4 25  8 55 42
  546. 50  3 32 45 56 41 26  7
  547. 33 62 15 20  9 24 39 58
  548. 16 19 34 61 40 57 10 23
  549. 63 14 17 36 21 12 59 38
  550. 18 35 64 13 60 37 22 11 
  551.  
  552. References:
  553. ``The Construction of Magic Knight Tours,'' by T. H. Willcocks,
  554. J. Rec. Math. 1:225-233 (1968).
  555.  
  556. "Games Ancient and Oriental and How to Play Them"
  557. by Edward Falkener published by Dover in 1961 (first published 1892)
  558.  
  559. "Mathematical Magic Show", Martin Gardner, ch. 14
  560.  
  561. ==> competition/games/chess/mutual.stalemate.p <==
  562. What's the minimal number of pieces in a legal mutual stalemate?
  563.  
  564. ==> competition/games/chess/mutual.stalemate.s <==
  565. 6.  Here are three mutual stalemate positions.  Black is lower case
  566. in the diagrams.
  567.  
  568. W Kh8 e6 f7 h7  B Kf8 e7
  569.  
  570.     --+--+--+--+--+
  571.       |  | k|  | K|
  572.     --+--+--+--+--+
  573.       | p| P|  | P|
  574.     --+--+--+--+--+
  575.       | P|  |  |  |
  576.     --+--+--+--+--+
  577.       |  |  |  |  |
  578.  
  579. W Kb1  B Ka3 b2 b3 b4 a4
  580.  
  581.     |  |  |  
  582.     +--+--+--
  583.     | p| p|  
  584.     +--+--+--
  585.     | k| p|  
  586.     +--+--+--
  587.     |  | p|  
  588.     +--+--+--
  589.     |  | K|
  590.     +--+--+--
  591.   
  592. W Kf1  B Kh1 Bg1 f2 f3 h2
  593.  
  594.       |  |  |  |
  595.     --+--+--+--+
  596.       | p|  |  |
  597.     --+--+--+--+
  598.       | p|  | p|
  599.     --+--+--+--+
  600.       | K| b| k|
  601.     --+--+--+--+
  602.   
  603.  
  604. ==> competition/games/chess/queen.control.p <==
  605. How many queens does it take to attack or control the board?
  606.  
  607.  
  608. ==> competition/games/chess/queen.control.s <==
  609. Five queens are required to attack every square:
  610.  
  611.     1   2   3   4   5   6   7   8
  612.    ___ ___ ___ ___ ___ ___ ___ ___
  613. h |   |   |   |   |   |   |   |   |  
  614.    --- --- --- --- --- --- --- ---
  615. g |   |   |   | Q |   |   |   |   |
  616.    --- --- --- --- --- --- --- ---
  617. f |   |   |   | Q |   |   |   |   |
  618.    --- --- --- --- --- --- --- ---
  619. e |   |   |   | Q |   |   |   |   |
  620.    --- --- --- --- --- --- --- ---
  621. d |   |   |   | Q |   |   |   |   |
  622.    --- --- --- --- --- --- --- ---
  623. c |   |   |   |   |   |   |   |   |
  624.    --- --- --- --- --- --- --- ---
  625. b |   |   |   |   |   |   |   |   |
  626.    --- --- --- --- --- --- --- ---
  627. a |   |   |   | Q |   |   |   |   |
  628.    --- --- --- --- --- --- --- ---
  629.  
  630. There are other positions with five queens.
  631.  
  632. ==> competition/games/chess/queen.most.p <==
  633. How many non-mutually-attacking queens can be placed on various sized boards?
  634.  
  635. ==> competition/games/chess/queen.most.s <==
  636. On an regular chess board, at most eight queens of one color can be
  637. placed so that there are no mutual attacks.
  638.  
  639. Here is one configuration:
  640. -----------------
  641. |Q| | | | | | | |
  642. -----------------
  643. | | |Q| | | | | |
  644. -----------------
  645. | | | | |Q| | | |
  646. -----------------
  647. | | | | | | |Q| |
  648. -----------------
  649. | |Q| | | | | | |
  650. -----------------
  651. | | | | | | | |Q|
  652. -----------------
  653. | | | | | |Q| | |
  654. -----------------
  655. | | | |Q| | | | |
  656. -----------------
  657.  
  658. On an nxn board, if n is not divisible by 2 or 3, n^2 queens can be placed
  659. such that no two queens of the same color attack each other.
  660.  
  661. The proof is via a straightforward construction.  For n=1, the result
  662. is obviously true, so assume n>1 and n is not divisible by 2 or 3 (thus n>=5).
  663. Assume we are given n queens in each of these n "colors" (numbers):
  664.     0 1 2 ... n-1
  665.  
  666. The proof is by construction.  The construction is easier to see then to
  667. describe, we do both.  Here is what it looks like:
  668.  
  669.     0    1    2    3    4    ...    n-2    n-1
  670.     n-2    n-1    0    1    2    ...    n-4    n-3
  671.     n-4    n-3    n-2    n-1    0    ...    n-6    n-5
  672.     ...(move one row down => sub 2 (mod n); one col right => add 1 (mod n))
  673.     2    3    4    5    6    ...    0    1
  674.  
  675. People who know how a knight moves in chess will note the repetitive knight
  676. move theme connecting queens of the same color (especially after joining
  677. opposite edges of the board).
  678.  
  679. Now to describe this: place in each cell a queen whose "color" (number) is:
  680.     j - 2*i + 1 (mod n),
  681.     where i is the # of the row, and j is the # of the column.
  682.  
  683. Then no 2 queens of the same color are in the same:
  684.     row, column, or diagonal.
  685.  
  686. Actually, we will prove something stronger, namely that no 2 queens of the
  687. same color are on the same row, column, or "hyperdiagonal".  (The concept, if
  688. not the term, hyperdiagonal, goes back to 19th century.)  There are n
  689. hyperdiagonals of negative slope (one of them being a main diagonal) and n
  690. hyperdiagonals of positive slope (one of them being the other main diagonal).
  691. Definition:  for k in 0..n-1:
  692.     the k-th negative hyperdiagonal consists of cells (i,j),
  693.         where i-j=k (mod n)
  694.     the k-th positive hyperdiagonal consists of cells (i,j),
  695.         where i+j=k (mod n)
  696.     Then 0-th negative hyperdiagonal is simply the NW-SE main diagonal.
  697.     Then "1-th" positive hyperdiagonal is simply the SW-NE main diagonal.
  698.  
  699.     The other 2*(n-1) hyperdiagonals appear as 2 disconnected diagonal
  700.         fragments of cells, but if you join opposite edges of an nxn
  701.         board to each other, forming a sphere, these 2 fragments
  702.         become linearly connected forming a great circle.
  703.  
  704. Now to the proof:
  705.   1) First note that the above color assignment does indeed uniquely define the
  706.     color of a queen in each of the n^2 cells.
  707.  
  708.   2) no row contains 2 queens of the same color:
  709.     cells (i, a) and (i, b) contain queens of the same color =>
  710.         a-2i-1 = b-2i-1 (mod n) =>
  711.         a      = b (mod n) =>
  712.         a = b (since a,b are within 1..n)
  713.  
  714.   3) no column contains 2 queens of the same color:
  715.     cells (a, j) and (b, j) contain queens of the same color =>
  716.         j-2a-1 = j-2b-1 (mod n) =>
  717.         2a     = 2b (mod n) =>
  718.         a      = b  (mod n)  (since n and 2 have no common factor) =>
  719.         a = b (since a,b are within 1..n)
  720.  
  721.   4) no negative hyperdiagonal contains 2 queens of the same color:
  722.     cells (a, j) and (b, k) on the same negative hyperdiagonal contain
  723.         queens of the same color =>
  724.         a-j    = b-k   (mod n) AND j-2a-1 = k-2b-1 (mod n) =>
  725.         2a-2j  = 2b-2k (mod n) AND j-2a = k-2b (mod n) =>
  726.         (adding corresponding sides:)
  727.         -j     = -k (mod n) =>
  728.         j = k.
  729.         And thus a = b, as well (see first equality, 5th line up)
  730.         
  731.   5) no positive hyperdiagonal contains 2 queens of the same color:
  732.     cells (a, j) and (b, k) on the same positive hyperdiagonal contain
  733.         queens of the same color =>
  734.         a+j    = b+k   (mod n) AND j-2a-1 = k-2b-1 (mod n) =>
  735.         2a+2j  = 2b+2k (mod n) AND j-2a = k-2b (mod n) =>
  736.         (adding corresponding sides:)
  737.         3j     = 3k (mod n) =>
  738.         j      = k (mod n)  (since n and 3 have no common factor) =>
  739.         j = k.  Likewise a = b.
  740.         
  741. As special cases with the 0th negative hyperdiagonal and 1st positive
  742. hyperdiagonal, no 2 queens on the same main diagonal are colored the same.
  743.  
  744. Now is this condition, than n be not divisible by 2 and 3 also *necessary*?
  745.  
  746. Mike Konrad
  747. mdk@sei.cmu.edu
  748.  
  749. ******
  750.  
  751.  . . . o .  This is a solution for the 5-queen problem
  752.  o . . . .  at the torus. It has the 90 degree rotation symmetry.
  753.  . . o . .
  754.  . . . . o
  755.  . o . . .
  756.  
  757.  According to T. Klove, The modular n-queen problem II,
  758.               Discrete Math. 36 (1981) 33
  759.  it is unknown how to construct symmetric (90 rot) solutions for 
  760.  n = 1 or 5 (mod 12) and n has prime factors = 3 (mod 4).
  761.  He solved the smallest cases 49 and 77.
  762.  Try the next cases 121 and 133 or find a general solution.
  763.  
  764. A further reference for modular or reflected queen problems is:
  765. Martin Gardner, Fractal Music, Hypercards and More ..., Freeman (1991)
  766.  
  767. ********
  768.  
  769. For the 3-D N-queens problem the answer is four, at (1,1,2), (1,3,3),
  770. (2,3,1), and (3,2,3).
  771.  
  772. You can't have more because with four, you must have at least two in
  773. at least one of the three horizontal slices of the cube.  For the
  774. two-or-more-queen slice you must solve the n-queens problem for a 3x3
  775. planar board, which allows you to place at most 2 queens, and one must
  776. be in a corner.  The two queens cover all but one spot in the adjacent
  777. slice, so if the two-queen slice is the middle one we're already 
  778. limited to no more than 4 queens.  But if we put the 2-queen slice at
  779. the bottom or top, then the corner queen has line of sight to all 
  780. corners of the opposite slice, so it can contain at most one queen,
  781. and so can the middle slice.
  782.  
  783. If they sit in a 4x4x4 cube, the maximum is 7.  Here is a sample.
  784.  
  785. 1. 4 4 3
  786. 2. 2 3 4
  787. 3. 1 2 2
  788. 4. 2 4 2
  789. 5. 3 2 1
  790. 6. 1 1 4
  791. 7. 3 1 3
  792.  
  793. If they sit in a 5x5x5 cube, the maximum is 13.  Here is a sample.
  794.  
  795. 1. 4 5 4
  796. 2. 3 5 1
  797. 3. 5 4 2
  798. 4. 3 1 2
  799. 5. 2 1 4
  800. 6. 2 5 5
  801. 7. 4 1 5
  802. 8. 1 5 2
  803. 9. 5 2 1
  804. 10. 2 3 1
  805. 11. 1 3 5
  806. 12. 1 1 1
  807. 13. 5 1 3
  808.  
  809. ==> competition/games/chess/queens.p <==
  810. How many ways can eight queens be placed so that they control the board?
  811.  
  812. ==> competition/games/chess/queens.s <==
  813. 92.  The following program uses a backtracking algorithm to count positions:
  814.  
  815. #include <stdio.h>
  816.  
  817. static int count = 0;
  818.  
  819. void try(int row, int left, int right) {
  820.    int poss, place;
  821.    if (row == 0xFF) ++count;
  822.    else {
  823.       poss = ~(row|left|right) & 0xFF;
  824.       while (poss != 0) {
  825.          place = poss & -poss;
  826.          try(row|place, (left|place)<<1, (right|place)>>1);
  827.          poss &= ~place;
  828.          }
  829.       }
  830.    }
  831.  
  832. void main() {   
  833.    try(0,0,0);
  834.    printf("There are %d solutions.\n", count);
  835.    }
  836. --
  837. Tony Lezard IS tony@mantis.co.uk OR tony%mantis.co.uk@uknet.ac.uk
  838. OR EVEN arl10@phx.cam.ac.uk if all else fails.
  839.  
  840. ==> competition/games/chess/rook.paths.p <==
  841. How many non-overlapping paths can a rook take from one corner to the opposite
  842. on an MxN chess board?
  843.  
  844. ==> competition/games/chess/rook.paths.s <==
  845. For a 1 x 1 chessboard, there are 1 unique paths.
  846. For a 1 x 2 chessboard, there are 1 unique paths.
  847. For a 1 x 3 chessboard, there are 1 unique paths.
  848. For a 1 x 4 chessboard, there are 1 unique paths.
  849. For a 1 x 5 chessboard, there are 1 unique paths.
  850. For a 1 x 6 chessboard, there are 1 unique paths.
  851. For a 1 x 7 chessboard, there are 1 unique paths.
  852. For a 1 x 8 chessboard, there are 1 unique paths.
  853. For a 2 x 2 chessboard, there are 2 unique paths.
  854. For a 2 x 3 chessboard, there are 4 unique paths.
  855. For a 2 x 4 chessboard, there are 8 unique paths.
  856. For a 2 x 5 chessboard, there are 16 unique paths.
  857. For a 2 x 6 chessboard, there are 32 unique paths.
  858. For a 2 x 7 chessboard, there are 64 unique paths.
  859. For a 2 x 8 chessboard, there are 128 unique paths.
  860. For a 3 x 3 chessboard, there are 12 unique paths.
  861. For a 3 x 4 chessboard, there are 38 unique paths.
  862. For a 3 x 5 chessboard, there are 125 unique paths.
  863. For a 3 x 6 chessboard, there are 414 unique paths.
  864. For a 3 x 7 chessboard, there are 1369 unique paths.
  865. For a 3 x 8 chessboard, there are 4522 unique paths.
  866. For a 4 x 4 chessboard, there are 184 unique paths.
  867. For a 4 x 5 chessboard, there are 976 unique paths.
  868. For a 4 x 6 chessboard, there are 5382 unique paths.
  869. For a 4 x 7 chessboard, there are 29739 unique paths.
  870. For a 4 x 8 chessboard, there are 163496 unique paths.
  871. For a 5 x 5 chessboard, there are 8512 unique paths.
  872. For a 5 x 6 chessboard, there are 79384 unique paths.
  873. For a 5 x 7 chessboard, there are 752061 unique paths.
  874.  
  875. /***********************
  876.  * RookPaths.c
  877.  * By: David Blume
  878.  * dcb@wdl1.wdl.loral.com (Predecrement David)
  879.  *
  880.  * How many unique ways can a rook move from the bottom left corner
  881.  * of a m * n chess board to the top right right?
  882.  *
  883.  * Contraints: The rook may not passover a square it has already visited.
  884.  *             What if we don't allow Down & Left moves? (much easier)
  885.  *
  886.  * This software is provided *as is.*  It is not guaranteed to work on
  887.  * any platform at any time anywhere. :-)  Enjoy.
  888.  ***********************/
  889.  
  890. #include <stdio.h>
  891.  
  892. #define kColumns 8            /* The maximum number of columns */
  893. #define kRows     8            /* The maximum number of rows */
  894.  
  895. /* The following rule is for you to play with. */
  896. #define kAllowDownLeft        /* Whether or not to allow the rook to move D or L */
  897.  
  898. /* Visual feedback defines... */
  899. #undef kShowTraversals        /* Whether or nor to show each successful graph */
  900. #define kListResults        /* Whether or not to list each n * m result */
  901. #define kShowMatrix            /* Display the final results in a matrix? */
  902.  
  903. char gmatrix[kColumns][kRows];                /* the working matrix */
  904. long result[kColumns][kRows];                /* the result array */
  905.  
  906. /*********************
  907.  * traverse
  908.  *
  909.  * This is the recursive function
  910.  *********************/
  911. traverse (short c, short r, short i, short j )
  912. {
  913.     
  914.     /* made it to the top left! increase result, retract move, and return */
  915.     if (i == c && j == r) {
  916.  
  917. #ifdef kShowTraversals    
  918.         short ti, tj;
  919.         gmatrix[i][j] = 5;
  920.         for (ti = c; ti >= 0; ti--) {
  921.             for (tj = 0; tj <= r; tj++) {
  922.                 if (gmatrix[ti][tj] == 0)
  923.                     printf(". ");
  924.                 else if (gmatrix[ti][tj] == 1)
  925.                     printf("D ");
  926.                 else if (gmatrix[ti][tj] == 2)
  927.                     printf("R ");
  928.                 else if (gmatrix[ti][tj] == 3)
  929.                     printf("L ");
  930.                 else if (gmatrix[ti][tj] == 4)
  931.                     printf("U ");
  932.                 else if (gmatrix[ti][tj] == 5)
  933.                     printf("* ");
  934.                 }
  935.             printf("\n");
  936.             }
  937.         printf("\n");
  938. #endif
  939.  
  940.         result[i][j] = result[i][j] + 1;
  941.         gmatrix[i][j] = 0;
  942.         return;
  943.         }
  944.     
  945.     /* try to move, left up down right */
  946. #ifdef kAllowDownLeft
  947.     if (i != 0 && gmatrix[i-1][j] == 0) {        /* left turn */
  948.         gmatrix[i][j] = 1;
  949.         traverse(c, r, i-1, j);
  950.         }
  951. #endif
  952.     if (j != r && gmatrix[i][j+1] == 0) {        /* turn up */
  953.         gmatrix[i][j] = 2;
  954.         traverse(c, r, i, j+1);
  955.         }
  956. #ifdef kAllowDownLeft
  957.     if (j != 0 && gmatrix[i][j-1] == 0) {        /* turn down */
  958.         gmatrix[i][j] = 3;
  959.         traverse(c, r, i, j-1);
  960.         }
  961. #endif
  962.     if (i != c && gmatrix[i+1][j] == 0) {        /* turn right */
  963.         gmatrix[i][j] = 4;
  964.         traverse(c, r, i+1, j);
  965.         }
  966.     
  967.     /* remove the marking on this square */
  968.     gmatrix[i][j] = 0;
  969.  
  970. }
  971.  
  972. main()
  973. {
  974.     short i, j;
  975.     
  976.     /* initialize the matrix to 0 */
  977.     for (i = 0; i < kColumns; i++) {
  978.         for (j = 0; j < kRows; j++) {
  979.             gmatrix[i][j] = 0;
  980.             }
  981.         }
  982.     
  983.     /* call the recursive function */
  984.     for (i = 0; i < kColumns; i++) {
  985.         for (j = 0; j < kRows; j++) {
  986.             if (j >= i) {
  987.                 result[i][j] = 0;
  988.                 traverse (i, j, 0, 0);
  989. #ifdef kListResults
  990.                 printf("For a %d x %d chessboard, there are %d unique paths.\n",
  991.                         i+1, j+1, result[i][j]); fflush(stdout);
  992. #endif
  993.                 }
  994.             }
  995.         }
  996.     /* print out the results */
  997. #ifdef kShowMatrix
  998.     printf("\n");
  999.     for (i = 0; i < kColumns; i++) {
  1000.         for (j = 0; j < kRows; j++) {
  1001.             short min = (i < j) ? i : j ;
  1002.             short max = (i < j) ? j : i ;
  1003.             printf("%6d", result[min][max]);
  1004.             }
  1005.         printf("\n");
  1006.         }
  1007. #endif
  1008. }
  1009.  
  1010. ==> competition/games/chess/size.of.game.tree.p <==
  1011. How many different positions are there in the game tree of chess?
  1012.  
  1013. ==> competition/games/chess/size.of.game.tree.s <==
  1014. Consider the following assignment of bit strings to square states:
  1015.  
  1016.     Square State        Bit String
  1017.     ------ -----        --- ------
  1018.  
  1019.     Empty            0
  1020.     White Pawn        100
  1021.     Black Pawn        101
  1022.     White Rook        11111
  1023.     Black Rook        11110
  1024.     White Knight        11101
  1025.     Black Knight        11100
  1026.     White Bishop        11011
  1027.     Black Bishop        11010
  1028.     White Queen        110011
  1029.     Black Queen        110010
  1030.     White King        110001
  1031.     Black King        110000
  1032.  
  1033. Record a position by listing the bit string for each of the 64 squares.
  1034. For a position with all the pieces still on the board, this will take
  1035. 164 bits.  As pieces are captured, the number of bits needed goes down.
  1036. As pawns promote, the number of bits go up.  For positions where a King
  1037. and Rook are in position to castle if castling is legal, we will need
  1038. a bit to indicate if in fact castling is legal.  Same for positions
  1039. where an en-passant capture may be possible.  I'm going to ignore these
  1040. on the grounds that a more clever encoding of a position than the one
  1041. that I am proposing could probably save as many bits as I need for these
  1042. considerations, and thus conjecture that 164 bits is enough to encode a
  1043. chess position.
  1044.  
  1045. This gives an upper bound of 2^164 positions, or 2.3x10^49 positions.
  1046.  
  1047. Jurg Nievergelt, of ETH Zurich, quoted the number 2^70 (or about 10^21) in
  1048. e-mail, and referred to his paper "Information content of chess positions",
  1049. ACM SIGART Newsletter 62, 13-14, April 1977, to be reprinted in "Machine
  1050. Intelligence" (ed Michie), to appear 1990.
  1051.  
  1052. Note that this latest estimate, 10^21, is not too intractable:
  1053. 10^7 computers running at 10^7 positions per second could scan those
  1054. in 10^7 seconds, which is less than 6 months.
  1055.  
  1056. In fact, suppose there is a winning strategy in chess for white.
  1057. Suppose further that the strategy starts from a strong book opening,
  1058. proceeds through middle game with only moves that Deep Thought (DT)
  1059. would pick using the singular extension technique, and finally ends in
  1060. an endgame that DT can analyze completely.  The book opening might take
  1061. you ten moves into the game and DT has demonstrated its ability to
  1062. analyze mates-in-20, so how many nodes would DT really have to visit?
  1063. I suggest that by using external storage such a optical WORM memory,
  1064. you could easily build up a transposition table for such a midgame.  If
  1065. DT did not find a mate, you could progressively expand the width of the
  1066. search window and add to the table until it did.  Of course there would
  1067. be no guarantee of success, but the table built would be useful
  1068. regardless.  Also, you could change the book opening and add to the
  1069. table.  This project could continue indefinitely until finally it must
  1070. solve the game (possibly using denser and denser storage media as
  1071. technology advances).
  1072.  
  1073. What do you think?
  1074.  
  1075. -------
  1076.  
  1077. I think you are a little bit too optimistic about the feasibility.  Solving
  1078. mate-in-19 when the moves are forcing is one thing, but solving mate-in-19
  1079. when the moves are not forcing is another.  Of course, human beings are no
  1080. better at the latter task.  But to solve the game in the way you described
  1081. would seem to require the ability to handle the latter task.  Anyway, we
  1082. cannot really think about doing the sort of thing you described; DT is just a
  1083. poor man's chess machine project (relatively speaking).
  1084.                         --Hsu
  1085.  
  1086. i dont think that you understand the numbers involved.
  1087. the size of the tree is still VERY large compared to all
  1088. the advances that you cite. (speed of DT, size of worms,
  1089. endgame projects, etc) even starting a project will probably
  1090. be a waste of time since the next advance will overtake it
  1091. rather than augment it. (if you start on a journey to the
  1092. stars today, you will be met there by humans)
  1093. ken
  1094.  
  1095. ==> competition/games/cigarettes.p <==
  1096. The game of cigarettes is played as follows:
  1097. Two players take turns placing a cigarette on a circular table.  The cigarettes
  1098. can be placed upright (on end) or lying flat, but not so that it touches any
  1099. other cigarette on the table.  This continues until one person loses by not
  1100. having a valid position on the table to place a cigarette.
  1101.  
  1102. Is there a way for either of the players to guarantee a win?
  1103.  
  1104. ==> competition/games/cigarettes.s <==
  1105. The first person wins by placing a cigarette at the center of the table,
  1106. and then placing each of his cigarettes in a position symmetric (with
  1107. respect to the center) to the place the second player just moved.  If the
  1108. second player could move, then symmetrically, so can the first player.
  1109.  
  1110. ==> competition/games/connect.four.p <==
  1111. Is there a winning strategy for Connect Four?
  1112.  
  1113. ==> competition/games/connect.four.s <==
  1114. An AI program has solved Connect Four for the standard 7 x 6 board.
  1115. The conclusion: White wins, was confirmed by the brute force check made by
  1116. James D. Allen, which has been published in rec.games.programmer.
  1117.  
  1118. The program called VICTOR consists of a pure knowledge-based evaluation
  1119. function which can give three values to a position: 
  1120.  1 won by white,
  1121.  0 still unclear.
  1122. -1 at least a draw for Black,
  1123.  
  1124. This evaluation function is based on 9 strategic rules concerning the game,
  1125. which all nine have been (mathematically) proven to be correct.
  1126. This means that a claim made about the game-theoretical value of a position
  1127. by VICTOR, is correct, although no search tree is built.
  1128. If the result 1 or -1 is given, the program outputs a set of rules applied,
  1129. indicating the way the result can be achieved.
  1130. This way one evaluation can be used to play the game to the end without any
  1131. extra calculation (unless the position was still unclear, of course).
  1132.  
  1133. Using the evaluation function alone, it has been shown that Black can at least
  1134. draw the game on any 6 x (2n) board. VICTOR found an easy strategy for
  1135. these boardsizes, which can be taught to anyone within 5 minutes. Nevertheless,
  1136. this strategy had not been encountered before by any humans, as far as I know.
  1137.  
  1138. For 7 x (2n) boards a similar strategy was found, in case White does not
  1139. start the game in the middle column. In these cases Black can therefore at
  1140. least draw the game.
  1141.  
  1142. Furthermore, VICTOR needed only to check a few dozen positions to show
  1143. that Black can at least draw the game on the 7 x 4 board.
  1144.  
  1145. Evaluation of a position on a 7 x 4 or 7 x 6 board costs between 0.01 and 10
  1146. CPU seconds on a Sun4.
  1147.  
  1148. For the 7 x 6 board too many positions were unclear. For that reason a
  1149. combination of Conspiracy-Number Search and Depth First Search was used
  1150. to determine the game-theoretical value. This took several hundreds of hours
  1151. on a Sun4.
  1152.  
  1153. The main reason for the large amount of search needed, was the fact that in 
  1154. many variations, the win for White was very difficult to achieve. 
  1155. This caused many positions to be unclear for the evaluation function.
  1156.  
  1157. Using the results of the search, a database will be constructed
  1158. of roughly 500.000 positions with their game-theoretical value. 
  1159. Using this datebase, VICTOR can play against humans or other programs, 
  1160. winning all the time (playing White).  The average move takes less 
  1161. than a second of calculation (search in the database or evaluation 
  1162. of the position by the evaluation function).
  1163.  
  1164. Some variations are given below (columns and rows are numbered as is customary
  1165. in chess):
  1166.  
  1167. 1. d1, ..  The only winning move.
  1168.  
  1169. After 1. .., a1 wins 2. e1. Other second moves for White has not been
  1170. checked yet.
  1171. After 1. .., b1 wins 2. f1. Other second moves for White has not been
  1172. checked yet.
  1173. After 1. .., c1 wins 2. f1. Only 2 g1 has not been checked yet. All other
  1174. second moves for White give Black at least a draw.
  1175. After 1. .., d2 wins 2. d3. All other second moves for White give black
  1176. at least a draw.
  1177.  
  1178. A nice example of the difficulty White has to win:
  1179.  
  1180. 1. d1, d2 
  1181. 2. d3, d4
  1182. 3. d5, b1
  1183. 4. b2!
  1184.  
  1185. The first three moves for White are forced, while alternatives at the
  1186. fourth moves of White are not checked yet.
  1187.  
  1188. A variation which took much time to check and eventually turned out
  1189. to be at least a draw for Black, was:
  1190.  
  1191. 1. d1, c1
  1192. 2. c2?, .. f1 wins, while c2 does not.
  1193. 2. .., c3 Only move which gives Black the draw.
  1194. 3. c4, .. White's best chance.
  1195. 3. .., g1!! Only 3 .., d2 has not been checked completely, while all
  1196.         other third moves for Black have been shown to lose.
  1197.  
  1198. The project has been described in my 'doctoraalscriptie' (Master thesis)
  1199. which has been supervised by Prof.Dr H.J. van den Herik of the
  1200. Rijksuniversiteit Limburg (The Netherlands).
  1201.  
  1202. I will give more details if requested.
  1203.  
  1204. Victor Allis.
  1205. Vrije Universiteit van Amsterdam.
  1206. The Netherlands.
  1207. victor@cs.vu.nl
  1208.  
  1209. ==> competition/games/craps.p <==
  1210. What are the odds in craps?
  1211.  
  1212. ==> competition/games/craps.s <==
  1213. The game of craps:
  1214. There is a person who rolls the two dice, and then there is the house.
  1215. 1) On the first roll, if a 7 or 11 comes up, the roller wins.
  1216.    If a 2, 3, or 12 comes up the house wins.
  1217.    Anything else is a POINT, and more rolling is necessary, as per rule 2.
  1218. 2) If a POINT appears on the first roll, keep rolling the dice.
  1219.    At each roll, if the POINT appears again, the roller wins.
  1220.    At each roll, if a 7 comes up, the house wins.
  1221.    Keep rolling until the POINT or a 7 comes up.
  1222.  
  1223. Then there are the players, and they are allowed to place their bets with
  1224. either the roller or with the house.
  1225.  
  1226. -----
  1227. My computations:
  1228.  
  1229.  
  1230.  
  1231.  
  1232.  
  1233. On the first roll, P.roller.trial(1) = 2/9, and P.house.trial(1) = 1/9.
  1234. Let  P(x) stand for the probability of a 4,5,6,8,9,10 appearing.
  1235. Then on the second and onwards rolls, the probability is:
  1236.  
  1237. Roller:
  1238.                          ---                        (i - 2)
  1239. P.roller.trial(i) =      \   P(x)   *   ((5/6 - P(x))         *   P(x)
  1240. (i > 1)                  /
  1241.                  ---
  1242.                  x = 4,5,6,8,9,10
  1243.  
  1244. House:
  1245.                         ---                        (i - 2)
  1246. P.house.trial(i) =      \   P(x)   *   ((5/6 - P(x))         *   1/6
  1247. (i > 1)                 /
  1248.                 ---
  1249.                 x = 4,5,6,8,9,10
  1250.  
  1251. Reasoning (roller): For the roller to win on the ith trial, a POINT
  1252. should have appeared on the first trial (the first P(x) term), and the
  1253. same POINT should appear on the ith trial (the last P(x) term). All the in
  1254. between trials should come up with a number other than 7 or the POINT
  1255. (hence the (5/6 - P(x)) term).
  1256. Similar reasoning holds for the house.
  1257.  
  1258. The numbers are:
  1259. P.roller.trial(i) (i > 1) =
  1260.  
  1261.                 (i-1)                 (i-1)                     (i-1)  
  1262.  1/72 * (27/36)      + 2/81 * (26/36)        + 25/648 * (25/36)
  1263.  
  1264.  
  1265. P.house.trial(i) (i > 1) =
  1266.  
  1267.                 (i-1)                 (i-1)                     (i-1)  
  1268.  2/72 * (27/36)      + 3/81 * (26/36)        + 30/648 * (25/36)
  1269.  
  1270.  
  1271. -------------------------------------------------
  1272. The total probability comes to:
  1273. P.roller = 2/9   +   (1/18 + 4/45 + 25/198)  = 0.4929292929292929..
  1274. P.house  = 1/9   +   (1/9  + 2/15 + 15/99)  =  0.5070707070707070..
  1275.  
  1276. which is not even.
  1277. ===========================================================================
  1278.  
  1279. ==
  1280. Avinash Chopde                 (with standard disclaimer)
  1281. abc@unhcs.unh.edu, abc@unh.unh.edu            {.....}!uunet!unh!abc
  1282.  
  1283. ==> competition/games/crosswords.p <==
  1284. Are there programs to make crosswords?  What are the rules for cluing cryptic
  1285. crosswords?  Is there an on-line competition for cryptic cluers?
  1286.  
  1287. ==> competition/games/crosswords.s <==
  1288. You need to read the rec.puzzles.crosswords FAQL.
  1289.